#define ElemType int

typedef struct ListNode List_Node;

#include "common.h"

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size);

int find(int* nums1, int idx1, int* nums2, int idx2, int k);

/* 
 * 本地debug通过, LC不行, 血压上来了
 */
int main()
{
	int nums1[2] = { 3, 4 }, nums2[0] = { };
	findMedianSortedArrays(nums1, 2, nums2, 0);
	return 0;
}

int nums1_len, nums2_len;
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
	nums1_len = nums1Size, nums2_len = nums2Size;
	int cond = nums1Size + nums2Size, total = cond >> 1;
	if (cond & 1) return find(nums1, 0, nums2, 0, total + 1);

	int left = find(nums1, 0, nums2, 0, total);
	int right = find(nums1, 0, nums2, 0, total + 1);
	return (double)left + right / 2;
}

int find(int* nums1, int idx1, int* nums2, int idx2, int k)
{
	if (nums1_len - idx1 > nums2_len - idx2) {
		int temp = nums1_len;
		nums1_len = nums2_len;
		nums2_len = temp;
		return find(nums2, idx2, nums1, idx1, k);
	}
	if (idx1 >= nums1_len) return nums2[idx2 + k - 1];
	if (k == 1) return nums1[idx1] < nums2[idx2] ? nums1[idx1] : nums2[idx2];
	else {
		int si = idx1 + k / 2, sj = idx2 + k - k / 2;
		if (nums1_len < si)
			si = nums1_len;
		if (nums1[si - 1] > nums2[sj - 1])
			return find(nums1, idx1, nums2, sj, k - (sj - idx2));
		else
			return find(nums1, si, nums2, idx2, k - (si - idx1));
	}
}
